package com.sheng.leetcode.year2025.month09.day06;

import org.junit.Test;

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author by ls
 * @date 2025/9/26
 * <p>
 * 3495. 使数组元素都变为零的最少操作次数<p>
 * <p>
 * 给你一个二维数组 queries，其中 queries[i] 形式为 [l, r]。<p>
 * 每个 queries[i] 表示了一个元素范围从 l 到 r （包括 l 和 r ）的整数数组 nums 。<p>
 * 在一次操作中，你可以：<p>
 * 选择一个查询数组中的两个整数 a 和 b。<p>
 * 将它们替换为 floor(a / 4) 和 floor(b / 4)。<p>
 * 你的任务是确定对于每个查询，将数组中的所有元素都变为零的 最少 操作次数。返回所有查询结果的总和。<p>
 * <p>
 * 示例 1：<p>
 * 输入： queries = [[1,2],[2,4]]<p>
 * 输出： 3<p>
 * 解释：<p>
 * 对于 queries[0]：<p>
 * 初始数组为 nums = [1, 2]。<p>
 * 在第一次操作中，选择 nums[0] 和 nums[1]。数组变为 [0, 0]。<p>
 * 所需的最小操作次数为 1。<p>
 * 对于 queries[1]：<p>
 * 初始数组为 nums = [2, 3, 4]。<p>
 * 在第一次操作中，选择 nums[0] 和 nums[2]。数组变为 [0, 3, 1]。<p>
 * 在第二次操作中，选择 nums[1] 和 nums[2]。数组变为 [0, 0, 0]。<p>
 * 所需的最小操作次数为 2。<p>
 * 输出为 1 + 2 = 3。<p>
 * <p>
 * 示例 2：<p>
 * 输入： queries = [[2,6]]<p>
 * 输出： 4<p>
 * 解释：<p>
 * 对于 queries[0]：<p>
 * 初始数组为 nums = [2, 3, 4, 5, 6]。<p>
 * 在第一次操作中，选择 nums[0] 和 nums[3]。数组变为 [0, 3, 4, 1, 6]。<p>
 * 在第二次操作中，选择 nums[2] 和 nums[4]。数组变为 [0, 3, 1, 1, 1]。<p>
 * 在第三次操作中，选择 nums[1] 和 nums[2]。数组变为 [0, 0, 0, 1, 1]。<p>
 * 在第四次操作中，选择 nums[3] 和 nums[4]。数组变为 [0, 0, 0, 0, 0]。<p>
 * 所需的最小操作次数为 4。<p>
 * 输出为 4。<p>
 * <p>
 * 提示：<p>
 * 1 <= queries.length <= 10^5<p>
 * queries[i].length == 2<p>
 * queries[i] == [l, r]<p>
 * 1 <= l < r <= 10^9<p>
 */
public class LeetCode3495 {

    @Test
    public void test() {
//        int[][] queries = {{1, 2}, {2, 4}};
        int[][] queries = {{2, 6}};
        System.out.println(new Solution().minOperations(queries));
    }
}

class Solution {
    public long minOperations(int[][] queries) {
        // 对于数组 queries[i] 中的元素，存在 [l, r]，这样一个区间，对于区间内的任意元素，都可以通过 floor(a / 4) 和 floor(b / 4) 来进行操作。
        // 每次操作时选择一个最大值和一个非0的最小值进行，这样操作次数最少。
        long ans = 0;
        for (int[] q : queries) {
            ans += (f(q[1]) - f(q[0] - 1) + 1) / 2;
        }
        return ans;
        // 超时
//        long ans = 0;
//        for (int[] query : queries) {
//            int l = query[0];
//            int r = query[1];
//            ans += calculateMinOperations(l, r);
//        }
//        return ans;
    }

    private long f(int n) {
        int m = 32 - Integer.numberOfLeadingZeros(n);
        long res = 0;
        for (int i = 1; i < m; i++) {
            res += (long) (i + 1) / 2 << (i - 1);
        }
        return res + (long) (m + 1) / 2 * (n + 1 - (1 << m >> 1));
    }

    /**
     * 计算区间 [l, r] 内所有数变为零的最少操作次数。
     * 使用贪心策略，每次操作选择最大的两个数进行处理。
     *
     * @param l 区间左边界
     * @param r 区间右边界
     * @return 最少操作次数
     */
    private long calculateMinOperations(int l, int r) {
        // 创建一个从大到小排序的队列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // 将区间内的元素添加到队列中
        for (int x = l; x <= r; x++) {
            maxHeap.add(x);
        }
        long operations = 0;
        // 区间内的元素不为空时，进行操作
        while (!maxHeap.isEmpty()) {
            // 弹出队列中的第一个元素
            int a = maxHeap.poll();
            if (a == 0) {
                continue;
            }
            // 获取操作过后的第一个元素
            int newA = a / 4;
            // 不为 0 时加入队列中
            if (newA > 0) {
                maxHeap.add(newA);
            }
            // 队列不为空时
            if (!maxHeap.isEmpty()) {
                // 弹出队列中的第二个元素
                int b = maxHeap.poll();
                if (b > 0) {
                    int newB = b / 4;
                    if (newB > 0) {
                        maxHeap.add(newB);
                    }
                }
            }
            // 一次操作
            operations++;
        }
        return operations;
    }
}
